package special;

class Trie {
    Node root;
    static class Node{
        boolean isEnd = false;
        Node[] have = new Node[26];
    }

    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        int len = word.length();
        int i = 0;
        Node cur = root;
        while (i < len){
            int c = word.charAt(i) - 'a';
            Node[] have = cur.have;
            if (have[c] == null){
                have[c] = new Node();
            }
            if (i == len - 1){
                if (!have[c].isEnd){
                    have[c].isEnd = true;
                }
            }
            cur = have[c];
            i++;
        }
    }
    
    public boolean search(String word) {
        int len = word.length();
        int i = 0;
        Node cur = root;
        while (i < len - 1){
            if (cur == null){
                return false;
            }
            int c = word.charAt(i) - 'a';
            cur = cur.have[c];
            i++;
        }
        return cur != null && cur.have[word.charAt(i) - 'a'] != null && cur.have[word.charAt(i) - 'a'].isEnd;
    }
    
    public boolean startsWith(String prefix) {
        int len = prefix.length();
        int i = 0;
        Node cur = root;
        while (i < len){
            int c = prefix.charAt(i) - 'a';
            cur = cur.have[c];
            if (cur == null){
                return false;
            }
            i++;
        }
        return true;
    }
}